The demand for privacy of digital data and algorithms for handling more and more complex structures has increased dramatically over the last decade. This demand goes hand in hand with the growth in communication capacity and its diverse applications. For securely storing and accessing both data and networks current technology offers several alternatives, such as encrypting data or data communication pathways. However critical problems arise when one needs to perform operations on the encrypted data or to enable the modification and/or the branching of various algorithms depending on the outcome of certain computations. In such cases, the encrypted data needs to be decrypted, processed as needed, and then re-encrypted, thereby exposing the encrypted data to potential misappropriation and theft.
For example, data storage and computing services such as cloud services provide a low cost solution to users to use their large shared resources for data storage and management. Cloud computing provides almost unlimited computing power to its users. It also provides other potential benefits to users in terms of instant availability, scalability and resource sharing. Cloud service provides offer the following cloud services to users which includes online file storage (for example, Dropbox), social networking sites (for example, Facebook), webmail (for example, Gmail), and online business application (for example, Brokerage). Although cloud computing has become a mature service model, the adoption of its services by customers (businesses, consumers) is limited by concerns about a loss of privacy of their private data.
Encryption of data could solve this issue, but if the clients want to manipulate their encrypted data in the cloud, they have to share the secret key with cloud provider to decrypt it before executing the required operations. In another approach of processing encrypted data, the encrypted data is transmitted back from the cloud to a client side, decrypted at the client side to process the resulting unencrypted data. This approach leads to several security issues as the cipher text is continuously exposed. Furthermore, if the computations are performed at the client side, the main objective of using the cloud computing is not achieved.
Homomorphic encryption is an appropriate solution to solve security issues, such as those related to cloud computing, since its schemes enable the performing of computations on encrypted data without sharing the secret key needed to decrypt the data. Specifically, in a homomorphic encryption system, if one encrypts plaintext data (P1) to yield encrypted data (E1), and then applies the same function to encrypt P2 to get E2 it follows that if E3 is computed through a specific polynomial function of E1 and E2, and, when decrypted, yields P3, then the same polynomial function applied to P1 and P2, would result in P3.
Homomorphic encryption can be categorized under three types of schemes with respect to the number of allowed operations on the encrypted data as follows: 1) Partially Homomorphic Encryption (PHE) allows only one type of operation with an unlimited number of times (that is, no bound on the number of usages); 2) Somewhat Homomorphic Encryption (SHE) allows a restricted set of operations a limited number of times, and 3) Fully Homomorphic Encryption (FHE) allows unlimited number of operations with unlimited number of times.
U.S. Pat. No. 8,565,435, issued on Oct. 22, 2013 to International Business Machines Corporation, discloses a partial homomorphic encryption and decryption method. However, the disclosed partial homomorphic system has numerous disadvantages that prevent it from being practically useful. For example, the partial homomorphic system is not homomorphic for operations other than multiplication and addition. Additionally, for the number of multiplication operations or the number of addition operations it is capable of doing, it is highly limited, resulting in only a SHE system.
Second, the disclosed partial homomorphic system attempts to mimic a fully homomorphic encryption system by using a technique called bootstrapping. In bootstrapping, a user homomorphically encrypts the key along with the message and when the ciphertext degrades as a result of too many addition or multiplication operations, the ciphertext is decrypted and then re-encrypted to remove the degradation. This dramatically increases the amount of memory, time, and processing needed to use the encrypted data.
Third, prior art attempts at homomorphic systems are not capable of operating rapidly enough to be commercially useful. For example, to encrypt 2 bytes (16 bits) of plaintext data and process it in its encrypted form can take up to 30 minutes of processing time on a multi-GHz CPU using prior art homomorphic approaches. Key generation can take even longer time and require multiple gigabytes of storage for only a 16-bit word encryption. Almost all servers, PCs and even smart phones now are built using either 64-bit or 32-bit CPUs. Going from 16-bit processing to 32-bit processing would require exponentially greater time and memory. Clearly, this performance metric effectively negates any practical application of existing homomorphic systems.
Also, a bottoms-up approach to developing an FHE scheme involves: choosing a well-defined and intensively researched hard mathematical problem. Based on this difficult mathematical problem, the following components need to be developed: Designing and Analysis of Key Generation Function, Designing and Analysis of Encryption Function, Designing and Analysis of Decryption Function, and Designing and Analysis of Evaluation Functions on encrypted data. This approach also requires addressing the following issues: development of security proof of the FHE scheme, and implementation of the FHE scheme on different hardware platforms with timing benchmarks. This approach for the designing of the FHE scheme requires considerable time and effort. Also, a challenge is for the security of the FHE scheme to stand a test of time. The cryptographic community spends years with a new cryptosystem before the community and the industry accepts the system as secure.
Accordingly, there is a need for a homomorphic encryption method that is scalable, can be used to rapidly and efficiently encrypt and decrypt, can also be used to rapidly and efficiently process encrypted data and can also operate over more than multiplication and addition, while at the same time being conservative with its need for computational space and processing power. The encryption function also needs to be very difficult to invert or break, while also allowing for various types of public and/or private key generation protocols to be supported without undermining homomorphism, speed, memory use, complexity or semantic security.
Additionally, there is also a need to take an existing conventional third-party cryptosystem that is already in use and considered to be secure by the cryptographic community and the industry in general and convert that into a highly efficient fully homomorphic solution. Stated differently, there is a need to enable homomorphic transformations of encrypted data, which is plaintext data encrypted with a conventional cryptographic scheme, such that operations can be performed on the encrypted data without first decrypting the data and yield the same result as if the operations were performed on the underlying plaintext data.